package algorithm.sort;

import java.util.*;

/**
 * put one value into the right position
 */
public class QuickSortTwo {

    private int[] quickSort(int []array, int start, int end) {

        if(start > end) {
            return array;
        }

        int tmp = array[start];
        int i = start;
        int j = end;

        while (i < j) {
            while (i <j && array[j] >= tmp) {
                j--;
            }

            while (i<j && array[i] <= tmp) {
                i ++;
            }

            if(i<j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //tmp应该在的位置,交换这两个元素
        array[start] = array[i];
        array[i] = tmp;


        quickSort(array, start, i-1);
        quickSort(array, j+1, end);
        return array;
    }

    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map =new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            int reduce = target - nums[i];
            if(map.get(reduce) != null) {
                return new int[]{map.get(reduce),i};
            } else {
                map.put(nums[i], i);
            }
        }

        return new int[]{-1,-1};

    }






    public static void main(String args[]) {

//        int []array = new int[]{6,1,2,7,9,3,4,5,10,8};
//
//        array = new QuickSortTwo().quickSort(array,0, array.length-1);
//        Arrays.stream(array).forEach(item->{
//            System.out.print(item + " ");
//        });
    }


}
